home *** CD-ROM | disk | FTP | other *** search
/ Computer Select (Limited Edition) / Computer Select.iso / dobbs / v17n04 / string.asc < prev    next >
Encoding:
Text File  |  1992-03-10  |  6.4 KB  |  202 lines
  1. _FINDING STRING DISTANCES_
  2. by Ray Valdes
  3.  
  4. [LISTING ONE]
  5.  
  6. /***********************************************************************
  7. LEVDIST.C -- Computing the Levenshtein distance (string-to-string edit)
  8.               by Ray Valdes, DDJ April 92
  9. ***********************************************************************/
  10.  
  11. #define TRUE     1
  12. #define FALSE    0
  13. #define private static
  14. #define public /**/
  15. typedef int bool;
  16.  
  17. private bool verbose_mode = TRUE;
  18.  
  19. typedef enum { MATCH, INS, DEL, SUB } opcode;
  20.  
  21. typedef struct
  22. {   int    cost;
  23.     char*  name;
  24.     int    delta_row;
  25.     int    delta_col;
  26. } operation;
  27.  
  28. #define COST(op)   (optable[(int)op].cost)  // for convenience
  29. #define OPSTR(op)  (optable[(int)op].name)  // for convenience
  30.  
  31. private operation optable[] =     //costs defined on a per-op basis
  32. {
  33.   /*--cost, name, delta_row, delta_col---------------------------------*/
  34.     { 0, "EQU", -1, -1},   /* a match or no-op backtracks to NorthWest */
  35.     { 1, "INS",  0, -1},   /* insert op backtrack to the West          */
  36.     { 1, "DEL", -1,  0},   /* delete op backstracks to the North       */
  37.     { 1, "SUB", -1, -1},   /* substitution op backtracks to NorthWest  */
  38. };
  39.  
  40. typedef struct
  41. {   int     distance;
  42.     opcode  op;
  43. } matrix_cell; 
  44.  
  45. #define NUM_ROWS 64
  46. #define NUM_COLS NUM_ROWS
  47. #define SIZEOF_STRING   NUM_ROWS
  48.  
  49. private char        A [SIZEOF_STRING];
  50. private char        B [SIZEOF_STRING];
  51. private matrix_cell M [NUM_ROWS] [NUM_COLS];  // this is The Matrix
  52.  
  53. #define DIST(i,j)  (M [(i)][(j)].distance)   // for convenience
  54. /****************************************************************/
  55.  
  56. private void       say_hello         (void);
  57. private bool       get_strings       (void);
  58. private void       initialize_matrix (void);
  59. private void       calculate_cell    (int row,int col);
  60. private void       print_cell        (int row,int col);
  61. private void       calculate_matrix  (int num_rows,int num_cols);
  62. private void       backtrack_matrix  (int num_rows,int num_cols);
  63. /****************************************************************/
  64. public int 
  65. main(int argc,char **argv)
  66. {   say_hello();
  67.     while(get_strings())
  68.     {   initialize_matrix();
  69.         calculate_matrix(strlen(A),strlen(B));
  70.         backtrack_matrix(strlen(A),strlen(B));
  71.     }
  72.     return 0;
  73. }
  74. /****************************************************************/
  75. private void 
  76. say_hello(void)
  77. {    if(verbose_mode) printf("\nLevenshtein distance, V1.0");
  78. }
  79. /****************************************************************/
  80. private bool 
  81. get_strings(void)
  82. {   char buffer[SIZEOF_STRING*3]; //arbitrarily big buffer
  83.     
  84.     printf("\nEnter  first string > "); gets(buffer);
  85.     if(buffer[0]=='\0') return FALSE;
  86.     strcpy(A,buffer);
  87.     printf("\nEnter second string > "); gets(buffer);
  88.     if(buffer[0]=='\0') return FALSE;
  89.     strcpy(B,buffer);
  90.     return TRUE;
  91. }
  92. /****************************************************************/
  93. private void 
  94. initialize_matrix(void)
  95. {   int row,col;
  96.  
  97.     for(row=0,col=0; col<NUM_COLS; col++)    // initialize the first row
  98.     {
  99.         M [row][col].distance  = col;
  100.         M [row][col].op        = INS;
  101.     }
  102.     for(row=0,col=0; row<NUM_ROWS; row++)    // initialize the first column
  103.     {
  104.         M [row][col].distance  = row;
  105.         M [row][col].op        = DEL;
  106.     }
  107. }
  108. /****************************************************************/
  109. private void 
  110. calculate_cell(int row,int col)
  111.  
  112. {   int dNorthWest = DIST(row-1, col-1);
  113.     int dWest      = DIST(row  , col-1);
  114.     int dNorth     = DIST(row-1, col  );
  115.  
  116.     if(dWest < dNorth)
  117.     {   if(dWest < dNorthWest)
  118.         {   M [row][col].op       = INS;
  119.             M [row][col].distance = dWest + COST(INS);
  120.         }
  121.         else                          // dNorthWest <= dWest < dNorth
  122.         {   opcode op;
  123.             op = ( A[row-1]==B[col-1] ) ? MATCH : SUB;
  124.             M [row][col].op       = op;
  125.             M [row][col].distance = dNorthWest +  COST(op);
  126.         }
  127.     }
  128.     else                             // dNorth <= dWest
  129.     {   if(dNorth < dNorthWest)
  130.         {   M [row][col].op       = DEL;
  131.             M [row][col].distance = dNorth + COST(DEL);
  132.         }
  133.         else                         // dNorthWest <= dNorth <= dWest
  134.         {   opcode op;
  135.             op = ( A[row-1]==B[col-1] ) ? MATCH : SUB;
  136.             M [row][col].op       = op;
  137.             M [row][col].distance = dNorthWest +  COST(op);
  138.         }
  139.     }
  140. }
  141. /****************************************************************/
  142. private void 
  143. calculate_matrix(int num_rows,int num_cols)
  144. {   int row,col;
  145.  
  146.     if(verbose_mode)
  147.     {   printf("\n\\\n  \\COL |");
  148.         for(col=0; col < num_cols+1; col++)
  149.             printf("____%d____|");
  150.         printf("\nROW \\  |         |");
  151.         for(col=1; col < num_cols+1; col++)
  152.             printf("    %c    |", B [col-1]);
  153.         printf("\n 0    \\|");
  154.         for(row=0,col=0; col < num_cols+1; col++)
  155.             print_cell(row,col);
  156.     }
  157.     for(row=1; row<num_rows+1; row++)
  158.     {   if(verbose_mode) printf("\n% 2d  %c  |",row, A [row-1]);
  159.         print_cell(row,0);
  160.         for(col=1; col<num_cols+1; col++)
  161.         {
  162.             calculate_cell(row,col);
  163.             if(verbose_mode) print_cell(row,col);
  164.         }
  165.     }
  166. }
  167.  
  168. /****************************************************************/
  169. private void 
  170. print_cell(int row,int col)
  171. {    printf("   %d %s  ",DIST(row,col),OPSTR( M [row][col].op));
  172. }
  173. /****************************************************************/
  174. private void 
  175. backtrack_matrix(int num_rows,int num_cols)
  176. {   int dx,dy;
  177.     int i,j;
  178.     int row = num_rows;
  179.     int col = num_cols;
  180.  
  181.     printf("\n\nLevenshtein distance is %d.\n",DIST(row,col));
  182.     printf("\nBacktrace:            %s",A);
  183.     
  184.     while(row>0 || col>0)
  185.     {   if( ( M [row][col].op != MATCH) && verbose_mode) 
  186.         {   printf("\nD(%d,%d)=%d    ", row,col,DIST(row,col));
  187.             printf("%s   --> ",OPSTR( M [row][col].op));
  188.             for(i=1;i<row-(M[row][col].op==DEL?1:0);i++)        
  189.                 printf("%c", A[i-1]);
  190.             /*printf("_");*/
  191.             for(j=col-(M[row][col].op==INS?1:0);j<num_cols+1;j++) 
  192.                 printf("%c", B[j-1]);   
  193.         }
  194.         dy = optable[(int)( M [row][col].op)].delta_row;
  195.         dx = optable[(int)( M [row][col].op)].delta_col;
  196.         row  += dy;
  197.         col  += dx;
  198.     }
  199. }
  200.  
  201.  
  202.